import numpy as np


def lcs(s1, s2, return_length=True):
    """最长公共序列"""
    size1 = len(s1) + 1
    size2 = len(s2) + 1
    chess = [[['', 0] for j in range(size2)] for i in range(size1)]
    for i in range(1, size1):
        chess[i][0][0] = s1[i - 1]
    for j in range(1, size2):
        chess[0][j][0] = s2[j - 1]

    for i in range(1, size1):
        for j in range(1, size2):
            if s1[i - 1] == s2[j - 1]:
                chess[i][j] = ['↖', chess[i - 1][j - 1][1] + 1]
            elif chess[i][j - 1][1] > chess[i - 1][j][1]:
                chess[i][j] = ['←', chess[i][j - 1][1]]
            else:
                chess[i][j] = ['↑', chess[i - 1][j][1]]

    i = size1 - 1
    j = size2 - 1
    s3 = []
    while i > 0 and j > 0:
        if chess[i][j][0] == '↖':
            s3.append(chess[i][0][0])
            i -= 1
            j -= 1
        if chess[i][j][0] == '←':
            j -= 1
        if chess[i][j][0] == '↑':
            i -= 1
    s3.reverse()
    if return_length:
        return len(s3)
    else:
        return s3


def L2(s):
    return np.sqrt(np.sum(np.power(s, 2)))


def cosine_similarity(s1, s2):
    """
    余弦相似度
    @param s1: 序列1，list of float
    @param s1: 序列2，list of float
    """
    return np.dot(s1, s2) / (L2(s1) * L2(s2))


def euclidean_distance(s1, s2):
    """
    欧式距离
    @param s1: 序列1，list of float
    @param s1: 序列2，list of float
    """
    return np.sqrt(np.dot(s1, s2))


def edit_distance(s1, s2):
    """
    编辑距离
    @param s1: 序列1，list of float
    @param s1: 序列2，list of float
    """
    s1 = ' '.join([str(word) for word in s1])
    s2 = ' '.join([str(word) for word in s2])

    size1 = len(s1)
    size2 = len(s2)

    tmp = np.arange(size2 + 1)
    value = None

    for i in range(size1):
        tmp[0] = i + 1
        last = i
        for j in range(size2):
            if s1[i] == s2[j]:
                value = last
            else:
                value = 1 + min(last, tmp[j], tmp[j + 1])
            last = tmp[j + 1]
            tmp[j + 1] = value
    return value


